package alephnull;


/**
 * Awesome algorithm
 * @author Qu huanwen
 *
 */
public class AlephNull {

	public static void main(String[] args) {
		AlephNull a = new AlephNull();

		print(a.rational(1, 0));
		print(a.rational(1, 1));
		print(a.rational(1, 2));
		print(a.rational(4, 1));
		print(a.rational(4, 6));
		print(a.rational(5, 11));
		print(a.rational(8, 70));
		print(a.rational(10, 467));
		print(a.rational(23, 4190316));
		print(a.rational(30, 100));
	}

	private static void print(int[] a) {
		System.out.println("[" + a[0] + "," + a[1] + "]");
	}

	public int[] rational(int generation, int item) {
		int max = (int) Math.pow(2, generation - 1) + 1;
		if (item >= max)
			return new int[] { 0, 0 };
		if (generation == 1) {
			if (item == 0)
				return new int[] { 0, 1 };
			else
				return new int[] { 1, 0 };
		}
		if (item % 2 == 0) {
			return rational(generation - 1, item / 2);
		} else {
			int n = item / 2;
			int[] r1 = rational(generation - 1, n);
			int[] r2 = rational(generation - 1, n + 1);
			return new int[] { r1[0] + r2[0], r1[1] + r2[1] };
		}
	}
}
